// 设计一个栈，实现push，pop，top, getMin操作，其中getMin要求能在常数时间内实现

// 思路：堆栈，用用一个栈存储所有元素，另一个栈存储最小栈，只有当当前元素比最小栈栈顶元素小才会入最小栈
// 出栈的时候，需要判断是否和最小栈的栈顶相同，如果相同的话，同步删掉
// 时间复杂度：O(1)，所有操作的时间复杂度都是常数时间
// 空间复杂度：O(n)，stack的大小

function MinStack() {
    this.stack = []
    this.minStack = []
}

MinStack.prototype.push = function (val) {
    this.stack.push(val)
    // 这里不要用while
    if (!this.minStack.length || this.minStack[this.minStack.length - 1] >= val) {
        this.minStack.push(val)
    }
}

MinStack.prototype.pop = function () {
    let val = this.stack.pop()
    if (val === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop()
    }
    return val
}

MinStack.prototype.top = function () {
    return this.stack[this.stack.length - 1]
}

MinStack.prototype.getMin = function () {
    return this.minStack[this.minStack.length - 1]
}

// 使用示例
const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.getMin()); // 输出: -3
minStack.pop();
console.log(minStack.top());    // 输出: 0
console.log(minStack.getMin()); // 输出: -2